Given two singly linked lists L​1​​=$a​_1$​​→$a​_2$→⋯→$a​_{n-1}$​​→$a​_n$​​ and L​2​​=$b​_1​​$→$b​_2$​​→⋯→$b​_{m-1}$​​→$b​_m​​$​​. If n≥2m, you are supposed to reverse and merge the shorter one into the longer one to obtain a list like a​1​​→a​2​​→b​m​​→a​3​​→a​4​​→b​m−1​​⋯. For example, given one list being 6→7 and the other one 1→2→3→4→5, you must output 1→2→7→3→4→6→5.

Each input file contains one test case. For each case, the first line contains the two addresses of the first nodes of L​1​​ and L​2​​, plus a positive $N (≤10^5)$ which is the total number of nodes given. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

where Address is the position of the node, Data is a positive integer no more than 10​5​​, and Next is the position of the next node. It is guaranteed that no list is empty, and the longer list is at least twice as long as the shorter one.

For each case, output in order the resulting linked list. Each node occupies a line, and is printed in the same format as in the input.

给定两个链表，现在需要将短的链表按照如下的方法插入到长的链表中，首先将短链表逆序，然后每隔两个节点插入到长的链表中去。

我们使用list1和list2分别保存两个链表，这里假设list1保存的是短的，另外一种情况一样，使用result保存所有插入完毕的链表，其实可以分2种情形考虑这个问题，第一种就是list1还有节点需要插入，那么就把插入2个list2节点和1个list1节点看成一个原子操作，第二种情况就是list1没有节点插入了，那么就依次插入list2节点，直到完毕即可。具体做法如下：